package com.sunny.l50;

import java.util.ArrayList;

public class Solution {

    private TreeNode prev = null;

    ArrayList<TreeNode> list = new ArrayList<>();

    public void recoverTree(TreeNode root) {
        dfs(root);
        if(2 == list.size()){
            list.get(0).val = list.get(0).val^list.get(1).val;
            list.get(1).val = list.get(0).val^list.get(1).val;
            list.get(0).val = list.get(0).val^list.get(1).val;
        }else if(4 == list.size()){
            list.get(0).val = list.get(0).val^list.get(3).val;
            list.get(3).val = list.get(0).val^list.get(3).val;
            list.get(0).val = list.get(0).val^list.get(3).val;
        }
    }

    public void dfs(TreeNode node){
        if(null != node.left){
            dfs(node.left);
        }
        if(prev != null && prev.val > node.val){
            list.add(prev);
            list.add(node);
        }
        prev = node;
        if(null != node.right)
            dfs(node.right);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
